package CountofSmallerNumbersAfterSelf;

import java.util.ArrayList;
import java.util.List;

public class Solution {
	class Node{
		private Node left,right;
		private int value;
		private int count;
		private int ans;
		public Node(Node left, Node right, int value, int count, int ans) {
			super();
			this.left = left;
			this.right = right;
			this.value = value;
			this.count = count;
			this.ans = ans;
		}
		public Node getLeft() {
			return left;
		}
		public void setLeft(Node left) {
			this.left = left;
		}
		public Node getRight() {
			return right;
		}
		public void setRight(Node right) {
			this.right = right;
		}
		public int getValue() {
			return value;
		}
		public void setValue(int value) {
			this.value = value;
		}
		public int getCount() {
			return count;
		}
		public void setCount(int count) {
			this.count = count;
		}
		public int getAns() {
			return ans;
		}
		public void setAns(int ans) {
			this.ans = ans;
		}
		
	}
	private int find(Node now,int val,int ans){
		if (now.value==val){
			now.count++;
			return ans+now.ans;
		}
		else if (val<now.value){
			now.ans++;
			if (now.left==null)
			  {
				Node node=new Node(null, null, val, 1, 0);
				now.left=node;
				return ans;
			  }
			else return find(now.left,val,ans);
		}
		else{
			if (now.right==null)
			  {
				Node node=new Node(null, null, val, 1, 0);
				now.right=node;
				return ans+now.count+now.ans;
			  }
			else return find(now.right,val,ans+now.count+now.ans);
		}
	}
    public List<Integer> countSmaller(int[] nums) {
        Node root = null;
        int[] temp=new int[nums.length];
        for (int i=nums.length-1;i>=0;i--){
        	if (root==null){
        		root=new Node(null, null, nums[i], 1, 0);
        		temp[i]=0;
        	}
        	else{
        		temp[i]=find(root,nums[i],0);
        	}
        }
        List<Integer> result=new ArrayList<>();
        for (int i=0;i<nums.length;i++)
        	result.add(temp[i]);
        return result;
    }
    
    public static void main(String args[]){
    	int[] nums={26,78,27,100,33,67,90,23,66,5,38,7,35,23,52,22,83,51,98,69,81,32,78,28,94,13,2,97,3,76,99,51,9,21,84,66,65,36,100,41};
    	Solution so=new Solution();
    	so.countSmaller(nums);
    }
    
}